package Test_1120;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class BinaryTree {
    public static class TreeNode{
          public char val;//数据
          public TreeNode left;//左孩子
          public TreeNode right;//右孩子
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree(){
        //创建节点
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        //连接节点
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        return A;
    }

    // 前序遍历
    public void preOrder(TreeNode root){
        //判断是否有节点,没有返回
        if(root == null){
            return;
        }
        System.out.print(root.val+ " ");
        //遍历左子树
        preOrder(root.left);
        //遍历右子树
        preOrder(root.right);
    }
    // 中序遍历
    public void inOrder(TreeNode root){
        //判断是否有节点,没有返回
        if(root == null){
            return;
        }
        //遍历左子树
        inOrder(root.left);
        System.out.print(root.val+ " ");
        //遍历右子树
        inOrder(root.right);
    }
    // 后序遍历
    public void postOrder(TreeNode root){
        //判断是否有节点,没有返回
        if(root == null){
            return;
        }
        //遍历左子树
        postOrder(root.left);
        //遍历右子树
        postOrder(root.right);
        System.out.print(root.val+ " ");
    }
    public static int nodeSize=0;
    // 获取树中节点的个数
    public void size(TreeNode root){
        //判断是否有节点
        if(root==null){
            return ;
        }
        nodeSize++;
        //遍历左子树节点
        size(root.left);
        //遍历右子树节点
        size(root.right);
    }
   public int size2(TreeNode root){
        if(root==null){
            return 0;
        }
        return size2(root.left)+size2(root.right)+1;
    }
    // 获取叶子节点的个数
    //叶子：度为0的节点
    public static int leafSize=0;
   public void getLeafNodeCount(TreeNode root){
          if(root==null){
              return;
          }
          //叶：度为0，没有左子树和右子树
          if(root.right==null&&root.left==null){
              leafSize++;
          }
          //叶子数=右子树的叶子数+左子树的叶子数
          getLeafNodeCount(root.left);
          getLeafNodeCount(root.right);
    }
    public int getLeafNodeCount2(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.right==null&&root.left==null){
            return 1;
        }
        //叶子数=右子树的叶子数+左子树的叶子数
        return getLeafNodeCount2(root.left)+ getLeafNodeCount2(root.right);
    }
// 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k){
          if(root==null){
              return 0;
          }
          //当k==1时，表示当前要查找的层次
          if (k==1){
              return 1;

          }
          //递归左右子树，直到k==1，到查找的层次
          //后将左子树的该层次的节点数+右子树的该层次的节点数
          return getKLevelNodeCount(root.left,k-1)+
                  getKLevelNodeCount(root.right,k-1);
    }
    // 获取二叉树的高度
    //看左子树的高度和右子树的高度
    //取左子树和右子树中的最大高度
    public int getHeight(TreeNode root){
          if(root==null){
              return 0;
          }
          int leftheight=getHeight(root.left);
          int rightheight=getHeight(root.right);
          return Math.max(leftheight,rightheight)+1;
    }
    // 检测值为value的元素是否存在,在哪个节点
    public TreeNode find(TreeNode root, char val){
           if(root==null){
               return null;
           }
           if(root.val==val){
               return root;

           }
           TreeNode left=find(root.left,val);
           //如果目标在左子树，直接返回左节点
           if(left!=null){
               return left;
           }
           TreeNode right=find(root.right,val);
            //如果目标在右子树，直接返回左节点
           if(right!=null){
               return right;
           }
           //没有，返回null
           return null;
   }
    //层序遍历
    /*public void levelOrder(Node root){

    }*/
    // 判断一棵树是不是完全二叉树
   /* public boolean isCompleteTree(Node root){

    }*/
    //相同的树
    //一般是判断不相同的情况
    //如果都为空。那么相同
    //如果有一个为空，有一个不为null，返回
    public boolean isSameTree(TreeNode p, TreeNode q) {
           //判断结构是否相同
           if(p!=null && q==null|| p==null &&q!=null){
               return false;
               }
           //如果相同，想判断是否为空
           //判断是否为空，如果都为空，直接返回
          if(p==null && q==null){
            return true;
           }
          //判断值是否相同
           if(q.val!=p.val){
               return false;
           }
           //都不为空且值相同
           return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    //另一棵树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null){
            return false;
        }
        //判断节点是否相同
        if(isSameTree(root,subRoot))
            return true;
        //如果不相同，判断该节点左子树是否相同
        if(isSubtree(root.left,subRoot))
             return true;

        //如果不相同判断该节点右子树是否相同
        if(isSubtree(root.right,subRoot))
            return true;
         return false;
    }
    //翻转二叉树
    //不用考虑左右子树为不为空，直接翻转即可
    public TreeNode invertTree(TreeNode root) {
          if(root==null){
              return null;
          }
          //将左右子树进行翻转
             TreeNode tmp=null;
             tmp=root.left;
             root.left=root.right;
             root.right=tmp;
         invertTree(root.left);
         invertTree(root.right);
         return root;
    }
    //平衡二叉树：左右子树相差<=1
    //求左右子树的高度
  public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        //左子树和右子树是否也是平衡二叉树
        //Math.abs绝对值
        return Math.abs(leftHeight-rightHeight)<2
                &&isBalanced(root.left)&&isBalanced(root.right);
    }
    //对称二叉树
    //左子树等于右子树
    //右子树等于左子树
    public boolean isSymmetric(TreeNode root) {
           if(root==null){
               return true;
           }
           return isSymmetricChild(root.left,root.right);
    }
    //判断结构是否对称：
    //左子树的左子树是否等于右子树的右子树
    //左子树的右子树是否等于右子树的左子树
    //值是否相等
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        if(leftTree!=null && rightTree==null || leftTree==null && rightTree!=null){
                 return false;
        }
        if(leftTree==null && rightTree==null){
            return true;
        }
        if(leftTree.val!= rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right) &&
                isSymmetricChild(leftTree.right,rightTree.left);
    }
    //二叉树的遍历
    public int i=0;
    public TreeNode createTree(String str){
        TreeNode root=null;
        if(str.charAt(i)!='#'){
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=createTree(str);
            root.right=createTree(str);
        }else{
            i++;
        }
        return root;
    }
    //根据二叉树创建字符串
    public String tree2str(TreeNode root) {
          if(root==null){
              return null;
          }
          StringBuilder stringBuilder=new StringBuilder();
          tree2strChild(root,stringBuilder);
          return stringBuilder.toString();
    }
    public void tree2strChild(TreeNode t,StringBuilder stringBuilder){
        if(t==null){
          return;
        }
        stringBuilder.append(t.val);
        if(t.left!=null){
            stringBuilder.append("(");
            tree2strChild(t.left,stringBuilder);
            stringBuilder.append(")");
        }else{
            if(t.right==null){
                return;
            }else{
                stringBuilder.append("()");
            }
        }
        if(t.right!=null){
            stringBuilder.append("(");
            tree2strChild(t.right,stringBuilder);
            stringBuilder.append(")");
        }else{
            return ;

        }    }
    //最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
          if(root==null){
              return null;
          }
          if(root==p ||root==q){
              return root;
          }
          TreeNode leftTree=lowestCommonAncestor(root.left,p,q);
          TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
          if(leftTree!=null && rightTree!=null){
              return root;
          }else if(leftTree!=null){
              return leftTree;

          } else{
              return rightTree;
          }
    }
/*    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
          if(root==null){
              return null;
          }
          //
    }*/
}
